2011년도 운영체제 2학기 텀 프로젝트 3

<i-node를 이용한 파일 관리>

아이노드의 정의
아이노드(inode)는 UFS와 같은 전통적인 유닉스 계통 파일 시스템에서 사용하는 자료구조이다. 아이노드는 정규 파일, 디렉터리 등 파일 시스템에 관한 정보를 가지고 있다.
파일들은 각자 1개의 아이노드를 가지고 있으며, 아이노드는 소유자 그룹, 접근 모드(읽기, 쓰기, 실행 권한), 파일 형태, 아이노드 숫자(inode number, i-number, 아이넘버) 등 해당 파일에 관한 정보를 가지고 있다. 파일시스템 내의 파일들은 고유한 아이노드 숫자를 통해 식별 가능하다.
일반적으로 파일 시스템을 생성할 때 전체 공간의 약 1퍼센트를 아이노드를 위해 할당한다. 아이노드를 위한 공간이 한정되어 있는 만큼 파일시스템이 가질 수 있는 파일의 최대 개수도 한정되어 있다. 그러나 대부분의 경우, 사용자가 느끼기에 거의 무한개에 가까운 파일을 생성하고 관리할 수 있다.

I-node의 구조 개념

<i-node의 구조 및 블록과의 연결 관계>
위 그림에서 아이노드는 제일 왼쪽에 있는 커다란 블록이다. 아이노드는 한 파일에 대한 다양한 정보를 담고 있는데, 그 정보들은 아래와 같다. mode
파일과 관계된 접근과 실행 권한을 저장하는 16bit 플래그 조합이다.
이 모드에 줄 수 있는 플래그에는 다음과 같은 것이 있다.
<mode에 들어갈 수 있는 플래그의 종류>

우리가 흔히 아는 운영체제에서의 ‘777 모드’ 라는 것은, 0~8번 비트가 모두 1인 것으로, 이것을 3비트씩 끊어서 읽은 것을 가리킨다. 즉, 777 모드는 모든 사용자에 대해서 읽기, 쓰기, 실행을 허가하는 모드인 것이다.

Owner
파일에 대한 소유자의 아이디를 나타내는 항목이다.
이 파일과 관계된 그룹 소유자의 아이디를 나타내는 항목이다.

timestamps
파일을 최후로 갱신한 시간, 최후로 액세스한 시간, 아이노드를 최후로 갱신한 시간을 표시한다.

file address
파일의 실제 데이터가 담겨 있는 세컨드 스토리지의 주소 정보를 담고 있는 항목을 통틀어 가리킨다.

direct pointers
실제 데이터가 들어있는 블록 번호들을 보유하고 직접 가리킨다.

single indirect pointer
블록의 주소 정보들을 담고 있는 다른 블록을 가리킨다. 한 블록의 크기를 4kb라고 하고, 블록의 주소 정보가 32bit(4byte)에 저장된다면, 한 블록에는 최대 1024개의 실제 블록 주소 정보를 담을 수 있다. single indirect pointer가 가리키는 블록에는 실제 블록 주소를 저장한 주소 번호들이 저장되어 있다. 즉, 총 두 번의 포인터 이동을 통해 실제 파일의 데이터를 담고 있는 블록에 접근할 수 있다.

double indirect pointers
single indirect pointer와 블록 사이에 또 다른 블록을 하나를 더 넣은 형태. 즉, 총 세 번의 포인터 이동을 통해 실제 파일의 데이터를 담고 있는 블록에 접근할 수 있다.

triple indirect pointers
double indirect pointers와 블록 사이에 또 다른 블록 하나를 더 넣은 형태. 즉, 총 네 번의 포인터 이동을 통해 실제 파일의 데이터를 담고 있는 블록에 접근할 수 있다.

I-node 파일 할당 개념
파일 할당은 블록 단위로 이루어진다. 동적으로 이루어지며 블록들이 인접할 필요는 없다. i_block(file address) 배열은 파일 데이터가 있는 실제 블록을 가리키기도 하며, 파일 데이터를 가리키는 위치 블록을 가리키기도 해서 직, 간접적으로 파일 블록을 가리킨다. 즉 커널이 파일을 저장장치에 기록할 때 i_block 배열에는 파일의 데이터가 기록되어 있는 블록의 번호가 저장된다.
<file address의 상세도>
i_block 배열의 크기가 13이므로 배열만으로는 13개의 블록밖에 가리킬 수 없다.
만약 파일 크기가 block size*13 보다 크다면?
block size를 4kb로 가정하자. 60kb의 용량을 가진 파일이 있다면 i_block의 direct pointers인 i_block[0]~i_block[9]까지는 실제 파일 데이터가 있는 블록을 가리킨다. 그리고 40kb가 넘어가는 데이터부터는 데이터의 블록 위치를 i_block[10]에서 가리키는 것이 아니라, i_block[10]가 가리키는 블록에 있는 데이터가 바로 실제 데이터를 가리키는 포인터 배열이 된다.
즉, 11번째 블록에 들어갈 데이터의 주소는 i_block[10]가 가리키는 블록의 첫 4byte가 되는 것이다. 마찬가지로 12번째 블록에 들어갈 데이터 주소는 i_block[10]이 가리키는 블록의 5~8번째 byte가 된다.
위의 그림을 보면 i_block[10]가 가리키고 있는 블록은 파일 블록이 아닌 파일 블록을 가리키고 있는 위치 블록이다. 앞서 블록의 크기를 4kb로 가정하였으므로 위치블록은 1024개의 파일 블록을 가리킬 수 있다. 그러므로 i_block[10]를 통해 기록할 수 있는 데이터의 크기는 4096kb가 된다. 따라서 크기가 60kb인 파일을 읽어오는 경우에는 i_block[0]~i_block[10]까지 40kb를 읽어 들이고, 나머지 20kb는 i_block[10]가 가리키는 위치 블록 내의 상위 20byte(5개)의 블록 번호가 가리키는 파일 블록을 찾아가면 된다.
그렇다면 i_block의 상위 11개의 배열을 통해 5036kb가 넘는 파일은 어떻게 저장될 수 있을까? i_block[11]과 i_block[12]를 이용하여 위치블록을 더 늘이면 된다.
i_block[11]에서는 위치 블록의 개수가 늘어난 만큼 1024의 제곱의 크기로 파일 블록을 가리킬 수 있기 때문에 그만큼 기록할 수 있는 파일의 크기가 커지는 것이다.
i_block[11]의 경우 파일의 최대 크기는 1024 x 4096kb가 되고, 총 4gb를 저장할 수 있으며, i_block[12]의 경우 1024 x 4gb 이므로 4tb를 저장할 수 있다. 따라서 블록의 크기가 4kb인 경우 하나의 inode에서 저장할 수 있는 파일의 크기는 '40kb + 4096kb + 4gb + 4tb'가 되는 것이다.
이런 메커니즘은 작은 파일에 더 유리하다. 파일이 데이터 블록을 10개 이상 요구하지 않고 디스크에 두 번만 접근하면 모든 데이터를 얻을 수 있다. 한 번은 inode의 i_block 배열의 요소를 읽기 위해, 다른 한번은 요청한 데이터 블록을 읽기 위해서 이다. 더 큰 파일일 경우 요청한 블록을 읽으려면 연속적인 디스크 접근이 세 번 또는 네 번 정도 필요하다.
<파일의 최대 크기 – 블럭이 4K bytes이고, 주소 값이 32bit 일 경우>

목적
아이노드를 구현해봄으로써, 운영체제에서 파일을 처리하는 기본 방식을 이해할 수 있다. 그리고 아이노드를 바탕으로 간단한 파일 입출력을 시뮬레이션 해봄으로써 운영체제의 파일 시스템에 대해서도 이해할 수 있다.

구현 시나리오
구현 프로그램의 큰 그림은 다음과 같은 순서로 이루어진다.
사용자로부터 파일 생성, 삭제, 수정, 접근에 대한 입력을 받는다.
파일의 생성, 삭제의 경우 가상 하드의 비트맵을 보여주는 방식을 통해 아이노드를 통한 파일 관리가 이루어지고 있는 모습을 보여준다.
접근의 경우 해당 파일의 특정 byte를 입력하면, 해당 부분에 해당하는 블럭을 리턴하여 준다.

이때 각 파일에 대한 아이노드 정보를 채우기 위해서, 프로그램 시작 시 사용자의 아이디와 그룹을 선택한 다음 파일을 생성하게 된다. 그럼 아이노드에는 owner id, group id, ctime, mtime, atime을 넣을 수 있다. 단 이 프로젝트에서는 mode의 플래그를 넣음에 있어서 9-14번 비트까지는 무시한다. 즉, 사용자, 그룹, guest 유저에 대해서 권한을 설정하는 부분을 구현한다. 또한 link count 계수 역시 무시한다.
따라서 아이노드에 들어가는 필드는 owner id, gorup id, ctime, mtime, atime, file size, direct pointer, single indirect pointer, double indirect pointer, triple indirect pointer의 총 10개의 필드가 들어가게 된다.

이때, 블록에 대한 직접 연결과 간접 연결은 아래와 같은 그림과 같이 동작하게 된다.
<단: inode 부분을 VHDD 부분에 추가 시켜도 되고 아니면 따로 배열을 할당하여 도 상관 없음>
<가상 하드디스크 드라이브에서 inode의 동작 구조>

이때 사용되는 각 블록에 대한 구조체와 inode에 대한 구조체는 아래와 같이 정의한다.

마지막으로 프로그램의 input 과 output은 다음과 같이 정의된다.

input

프로그램을 처음 시작할 때 입력 받는 사용자 아이디와 그룹 아이디

파일을 생성할 때 입력 받는 파일의 이름과 크기 (크기는 정수로 받으며 단위는 1Kbyte 단위 이며 범위는 1~100)

파일을 삭제 할 때 입력 받는 파일의 이름

파일에 접근할 때 입력 받는 파일의 이름

output

파일의 정보 출력

파일의 이름, 크기, 수정 날짜, 소유자 아이디, 그룹 아이디 등과 같은 기본적인 아이노드 정보

할당된 블럭의 개수

아이노드 배열 및 가상 하드 디스크 드라이브의 정보

아이노드 배열의 남은 크기

가상 하드 디스크 드라이브의 남은 크기

하드 디스크의 비트맵 (MFC 등과 같은 윈도우 프로그램을 이용하여 시각적으로 표현. 선택사항. 구현 시 추가 점수)

I-node의 구조 부분에서 파일이름 부분을 내림차순 혹은 올림 차순으로 정렬 하여서 보여줌 (정렬을 고려 하여 입력을 받아도 무방함)

프로그램 요구사항

direct 필드의 개수는 총 10개 이고, indirect 필드는 single, double, triple이 각각 하나씩이다. 따라서 총 i_block의 크기는 13이다. 또한 한 하드 디스크의 한 블럭의 크기는  1Kbyte라고 가정한다.

가상 하드의 배열은 동적으로 할당하며, 그 크기는 1Gbytes로 한다.

가상하드에 넣는 가상 파일의 크기는 최대 100Kbyte를 넘지 않도록 한다. 단 VHDD를 채우는데 있어서 처음부터 빈곳을 확인을 하고 파일을 채워 나감

개발 환경

Platform : Windows

Dev. Language : C/C++(MFC 사용 권장-Console도 무방함)

제출 마감 기한
12월 3일 (월) 23:59 까지

텀 프로젝트 구성 인원
개인 별

제출 방식
소스와 실행 파일, 문서 파일을 압축하여 “Term03_학번_이름”으로 ftp://163.180.116.93

(ID :　os, PW : 1111)의 "TermProject_제출" 폴더에 업로드